\section{ПОЛУТОНОВЫЕ МАТРИЧНЫЕ ШТРИХКОДЫ: \\
СПЕЦИФИКАЦИЯ, РЕАЛИЗАЦИЯ}

\subsection{\textsc{Спецификация полутонового матричного 
штрихкода}}
\label{sec:spec}
\textbf{Полутоновый матричный штрихкод} 
(сокращённо HT-код, от англ. <<\textit{halftone}>>~---
полутоновый) представляет собой двумерный штрихкод общего назначения,
характерной особенность которого, по сравнению с другими штрихкодами,
является то, что каждый барсель может быть в более чем двух состояниях.

Матрица кода всегда квадратная размером от $14 \times 14$ до 
$202 \times 202$ c шагом 4. Предусмотрено 4 различных режима с 
2, 3, 4 и 8 градациями серого. Логически код делится на фрагменты
размером $4 \times 2$ (см. \figurename\ \ref{fig:codeGrid}). 
Фрагменты, расположенные в в трёх углах
кроме правого верхнего (на рисунке выделены) имеют особое назначение ---
в них содержится данные о формате сообщения.  

\begin{figure}[htb]
    \centering
    \includegraphics{img/codeGrid}
    \caption{Общий вид матрицы HT-кода}
    \label{fig:codeGrid}
\end{figure}   

Сообщение окружено рамкой толщиной 1 барсель аналогичной коду DataMatrix
(см. \figurename\ \ref{fig:dmPattern}). Назначение её двоякое: первое, 
L-образная сплошная часть помогает локализовать код, а чередование 
чёрного и белых барселей определяет размер матрицы.

\subsubsection{Определение байтов формата}
Расположение байтов, описывающих структуру сообщения, показано рисунке 
\ref{fig:codeGrid} (выделено серым). Для надёжности и выявления ошибок
сообщение о формате повторяется трижды --- в каждой из отмеченных областей.

Байты формата всегда кодируются в бинарном режиме (чёрный --- 1, белый --- 0), 
длинна~--- 3 
(с учётом повторений~--- 9). Биты в каждом фрагменте идут от старшего к 
младшему слева-направо и сверху-вниз.

Старший байт в верхнем углу находится слева. В нижних углах --- верхний байт над
двумя нижними байтами.

Сообщение формата кодирует следующую информацию:

\begin{itemize}
\item Длину сообщения в байтах без учёта коррекции ошибок (первые два байта).

\item Число уровней градации серого --- 2, 3, 4 или 8 (кодируется первыми двумя
битами последнего байта, описывающего формат: 2 -- 00, 3 -- 01, 4 -- 10, 8 -- 11)

\item Содержимое --- байты или текст в кодировке UTF-8 (если последний 
бит 1 --- текст, иначе --- байты).

\end{itemize} 

Остальные биты должны быть выставлены в 0.

\subsubsection{Определение байтов содержимого}

Пусть требуется закодировать исходное сообщение длинной $l$ байт. 
Отслеживание и восстановление ошибок производится с помощью кода 
Рида--Соломона (см \ref{sec:RSCode}).
Для 2 уровней яркости максимальная часть восстановимых байт ($r_2$) составляет
20\%, для 3 ($r_3$)~--- 25\%, для 4 ($r_4$)~--- 40\%, для 8 ($r_8$)~--- 45\%. 
Отсюда следует, что длинна сообщения вместе с байтами корректировки ошибок составляет
\begin{equation*}
d(l, u) = 2\lceil l r_u \rceil + l,
\end{equation*}
где $u$ --- текущий число уровней градации серого.

Таким образом, как было указано выше, барсели формируются 
в прямоугольники размером $4 \times 2$. 
Если $u = 2$, то число необходимых прямоугольников $w(l, u) = d(l, u)$ 
(для каждого байта отдельный прямоугольник), если $u=3$, то 
$w(l, u) = \lceil \frac{2 d(l, u)}{3}  \rceil$ (три байта на 2 прямоугольника),
если $u = 4$, то $w(l, u) = \lceil \frac{d(l, u)}{2}  \rceil$ (2 байта
в один прямоугольник), наконец, если $u = 8$, то 
$w(l, u) = \lceil \frac{d(l, u)}{4}  \rceil$ (4 байта в один прямоугольник).
После этого вычисляем размер матрицы
\begin{equation*}
m = 4 
    \left\lceil
        \sqrt{
            \left\lfloor
                \frac{w(u, l) + 10} {2}
            \right\rfloor
        }
    \right\rceil 
+ 2
\end{equation*}

Далее можно приступать к заполнению матрицы $m \times m$. Заполнение ведётся в 
$u$-ичной системе, причём белый цвет --- всегда нуль, чёрный --- $u-1$, остальные
значения равномерно распределены на промежутке $(0, 255)$. Матрица заполняется
сверху-вниз и слева-направо, пропуская клетки, заполненные данными о формате.
Каждый прямоугольник $4 \times 2$ (а для 3 уровней яркости --- два таких прямоугольника)
заполняется независимо. На все байты (в том числе и на данные о формате) накладывается
маска $A8_{16}$ оператором $\oplus$ --- <<исключающее или>>, для создания однородного
рисунка. Пустые прямоугольники заполняются случайными байтами.

Далее можно переходить к распечатке заполненной матрицы обеспечивая белые поля 
по периметру кода толщиной не менее 4 барселей. Ниже приведены примеры заполненных
матриц (рисунки \ref{fig:ht2}--\ref{fig:ht8}).

\begin{figure}[htb]
    \begin{multicols}{2}
 
        \begin{center}
             \includegraphics[scale=0.75]{img/long_2l} 
             \caption{HT-код с двумя уровнями}
             \label{fig:ht2}
        \end{center}
   
        \begin{center}
            \includegraphics[scale=0.75]{img/long_3l} 
            \caption{HT-код с тремя уровнями}
            \label{fig:ht3}
        \end{center}       
       
    \end{multicols}
\end{figure}

\begin{figure}[htb]
    \begin{multicols}{2}
 
        \begin{center}
             \includegraphics[scale=0.75]{img/long_4l} 
             \caption{HT-код с четырьмя уровнями}
             \label{fig:ht4}
        \end{center}
   
        \begin{center}
            \includegraphics[scale=0.75]{img/long_8l} 
            \caption{HT-код с восемью уровнями}
            \label{fig:ht8}
        \end{center}       
       
    \end{multicols}
\end{figure}

\subsection{\textsc{Реализации}}

В качестве основы взят проект \textit{ZXing} (см. \ref{sec:zxing}) 
на C++. Были дописаны следующие модули (см. приложения \ref{sec:apx1} и
\ref{sec:apx2}):

\begin{itemize}

\item \texttt{\small ReedSolomonEncoder} --- отвечает за кодирование информации
в соответствии методом Рида--Соломона (\ref{sec:RSCode}).

\item \texttt{\small detector} --- модуль-детектор. Выделяет в исходном полутоновом
изображении HT-код, проводит его перспективное преобразование так,
чтобы каждому пикселю в итоговом изображении соответствовал ровно один барсель
кода (см. также Рисунок \ref{fig:persTrans}).

\item \texttt{\small decoder} --- декодирует выделенное на предыдущем этапе 
изображение кода.

\item \texttt{\small encoder} --- производит кодирование данных в изображение
(это значит~--- в матрицу кода). 
\end{itemize}

Первый модуль в списке реализует реализован без каких любо особенностей
и рассматривать его не будем. Два последних модуля 
(см. классы \texttt{\small DecoderGC} и \texttt{\small EncoderGC} 
в приложении \ref{sec:apx2}) реализуют то, что описано в
\ref{sec:spec}. Для двух, четырёх, восьми уровней 
поток выполнения общий, для трёх, в силу особенностей, реализация
отдельная.

Для второго модуля, алгоритм следующий 
(см. класс \texttt{\small DetectorGC} в приложении \ref{sec:apx2}):

\begin{itemize}

\item На вход поступает полутоновое изображение (17--22).

\item Изображение передаётся классу \texttt{\small WhiteRectangleDetector}
для выделения четырёхугольника, содержащего код (26--35).

\item Пробегая по сторонам выделенного прямоугольника и считая чередования
чёрного и белого определяем размер матрицы кода, одновременно
определяем те стороны, где чередований нет~--- это будут границы
L-шаблона (29--163).
 
\item Зная координаты каждого из четырёх углов матрицы кода на рисунке,
вычисляем преобразование, переводящее его к первоначальному виду (165-166).

\item Из каждого барселя берём центральный пиксель, таким образом
имеем матрицу пикселей, соответствующую исходному коду (167).

\item Выравниваем контраст результата таким образом,
чтобы самому светлому пикселю соответствовало 255, самому тёмному --- 0
(линейное преобразование) (171, 222--253)

\item в результате имеем матрицу кода, а также четырёхугольник, 
ограничивающий код на рисунке.

\end{itemize}


\subsection{\textsc{Результаты, выводы}}

Заполним таблицу свойств\footnote{Дано для всех четырёх вариантов градаций серого.} 
HT-кода аналогичную таблице \ref{tbl:cmp}.

\begin{table}[htb]
	\centering
	\caption{Таблица свойств HT-кода}
	\begin{tabular}{|c|c|}
	\hline 
	 & \textbf{HT-код } \\ 
	\hline 
	Байты & 3565, 4990, 5545, 7880 \\ 
	\hline 
	Текст & 3565, 4990, 5545, 7880 \\ 
	\hline 
	Максимальный размер & $202 \times 202$  \\ 
	\hline 
	Эффективность кода & 0.70, 0.98, 1.09, 1.54\\ 
	\hline 
	Уровень коррекции ошибок & 20\%, 25\%, 40\%, 45\% \\
	\hline 
	Предельная эффективность кода & 0.71, 1.06, 1.11, 1.58\\ 
	\hline 
	\end{tabular} 
\end{table}

Отсюда видно, что выбранная методика оправдала себя --- удалось
поднять уровень эффективности полутонового кода выше 1, в то время
как для традиционных форматов она едва ли превосходит 0.8. 
Это позволяет увеличит длину сообщений приблизительно в полтора
раза при сравнительно тех же размерах. 

Если говорить о вопросе стабильности распознавания, то в целом, идёт
речь о физических свойствах сканирующего и печатающего устройств:
чем хуже качество изображений, тем ниже доля успешно декодированных 
матриц. Однако для полутоновых кодов имеет место одно очевидное правило:
чем больше уровней серого в коде, тем труднее распознавание. Практически,
в одном из испытаний результаты успешности декодирования следующие:
для двух уровней~--- 82\%, трёх~--- 75\%, четырёх~--- 56\%, восьми~---
10\%.

Таким образом, при обычных условиях полутоновые коды с числом уровней
более четырёх имеют малую ценность, а три уровня позволяют заметно 
увеличить эффективность кода без заметного падения доли 
успешно декодированных матриц.

Казалось бы, выход для значительного числа градаций серого прост~---
нивелировать низкую стабильность распознавания каждого отдельного барселя
увеличением числа байтов корректировки ошибок. Однако искажение считывания носит 
тотальный характер и, как показали эксперименты, такой подход не решает проблему.

Отдельно следует упомянуть о приемлемых линейных размерах матриц. 
Хотя спецификация в работе и указывает на максимальный размер равный 
$202 \times 202$, но едва ли удастся распознать такую матрицу не прибегая к
делению на части (чего, кстати, нет в описанной реализации). Большие матрицы 
не только трудно декодировать, но и трудно локализовать. Пожалуй,
для практических нужд следует быть менее амбициозными и ограничиться матрицами
размером до 100, причём они должны становиться меньше для кодов с б\'{о}льшими
линейными размерами (сказывается перепад яркости от края до края на больших 
площадях, что мешает правильно идентифицировать барсель).

Где же можно применить предложенный формат штрихкодов? В силу того, что
основным недостатком полутоновых кодов является некоторое ухудшение 
доли успешных распознаваний (при одинаковых условиях), то не следует
заменять их там, где свою функцию  выполняют традиционные штрихкоды.
HT-код следует применять в тех задачах, где объёмы информации значительны, а
сканирующее оборудование достаточно точно.   

Подводя черту под сказанным, отметим что идея использовать более двух градаций
серого для создания штрихкодов вполне жизнеспособна и настоящая работа есть тому
доказательство.
 